\documentclass[a4paper,11pt]{report}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[danish]{babel}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead[LE,LO]{\textbf{Compiler Construction}}
\fancyhead[RE,RO]{\textit{Philip Thyssen \& Michael Franz (Group 4)}}

\lstset{basicstyle=\footnotesize, tabsize=3, numbers=left, stepnumber=1}
\lstdefinelanguage{none}{morekeywords={thisisnotakeyword}}
\lstdefinelanguage{rajah}{morekeywords={func, end, int, bool, array, of,
record, type, var, return, write, allocate, if, then, while, do, length,
else, true, false, null, break, continue},
morecomment=[l]{\#}, morecomment=[n]{(*}{*)} }
\title{Compiler Construction, part 2}
\author{Philip Thyssen \& Michael Franz}
\date{Tuesday, Marts 2, 2011}

\begin {document} 
\maketitle
\renewcommand{\contentsname}{Table of contents}
\tableofcontents
\newpage
\section{Introduction}
In this part of the project Compiler construction, the task is to construct the scanner and parser phase. 
Furthermore an abstract syntax tree and a pretty-printer has to be written in order to present the scanned 
and parsed input in rajah syntax. 
\section{Scanner - Lexical Analysis}
The lexical analysis is done during the scanner phase. During this analysis every character in the input is 
analyzed and matched to a token or ignored. Every defined token has a predefined set of inputs that will be
 matched to it.  Keywords, identifiers, integers and operators will be scanned and should be recognized and 
returned with tokens identifying the type or in case of identifiers and integers return the value. Furthermore, 
the scanner is ignoring comments, both one line and multiline comments.
\subsection{Implementation}
To implement a scanner flex - Fast Lexical Analyzer, is used.  Flex is a tool for generating scanners. It generates
 a scanner based on rules, which a formed of pairs of a regular expression and c-code.  The regular expression is 
what the scanned input is matched against, whereas the c-code is the action taken corresponding to the matched input.
To show the principle, the rule for an identifier is shown:
\begin{lstlisting}
	Rule				Action
 [a-zA-Z_][a-zA-Z0-9_]* { yylval.stringconst = (char *)malloc(strlen(yytext)+1);
                         sprintf(yylval.stringconst,"%s",yytext); 
                         return tID; }
\end{lstlisting}
First, The regular expression which identifies with every input which starts with an letter and continued by any kind 
of letter and integer, followed by an action. In this case, memory is allocated for the input string and assigned to 
the union created in the bison file. Furthermore a printstatement is executed where the incoming string is placed in the memory allocated for
\textsl{yylval.stringconst} and the identifier tID, which is defined 
in the bison file, is returned.\\ 
The flex file contains three different states. The first state called initial, which is the main state where every input which has to be tokenized
is processed. The two other states, comment and one\_line\_comment is entered through initial. Those states can only be entered if the sign \textbf{\#} or 
\textbf{(*} is scanned. How these states are implemented is shown below, where multiline comments are used as an example. When the beginning of a comment section is recognized, 
a comment state is introduced: 
\begin{lstlisting}
 "(*"		{commentdepth= 1;BEGIN(comment);}

<comment>"(*" 	{commentdepth++;}
<comment>"*)" 	{commentdepth--;if(commentdepth==0){ BEGIN(INITIAL);}}
<comment>\n	{lineno++;}
<comment>.	/* ignore */ ;
\end{lstlisting}
The main idea within the comment states is to make sure that nested comments and comments filling out several lines are ignored.
 This is why there is a count variable keeping track on the numbers of begin and end comment signs. When the depth has reached zero 
the initial state. 
\section{Parsing - Syntatic Analysis }
The parser is the next step of creating a compiler which can create an executable program. Its purpose is to do a syntatic analysis using context-free grammar. Given a structue of a language, in this case Rajah, 
a grammar can be created which will ensure that the structure obeys the given language. Afterwards this grammar is used in the analysis to create an Abstract Syntax Tree. There are some issues that has to be 
considered. Ambiguity is one issue which has to be adressed, it's especially operators and nested if-else which would cause those situations. One can either rewrite part of the grammar or use bison's precedence assignments. Another issue
is if there are certain situations the grammar should not consider. For instance, every function has to end by the name of the function and every function has to have a return statement. These things can be dealt with in the parser or postponed.
It is very easy to verify that the functions ends with its name, which is why the parser is handling this. However making sure that a return statement is available is more difficult, due to several returns, which is why this part is postponed. 
\subsection{Precedence - Shift-reduce}
The problem of precedence shows in the form of shift-reduce conflict. A shift-reduce conflict is when a grammar rule allows to reduce and to shift, meaning either evaluate by one rule or continue by the same rule.
This is especially the case with operators. Therefore when a operator is parsed, it has to bind more or less tight, for instance multiplication and division superseeds addition and subtraction: 
\begin{verbatim}
 3 + 4*4  shoud look like 3 + (4*4)
\end{verbatim} 
Every operator has a left associativity except for \textbf{not}, the reason herefor is that \textbf{not} will always come before an expression which is why this expression has to be evaluated first. Below is a precedence table, where 
the predence table used in C has be used as inspiration.
\begin{center}
\begin{tabular}{ l r }
  Operator & Associativity \\
  ! & right-to-left \\
  * / & left-to-right \\
  + - & left-to-right \\
  < > <= >= & left-to-right \\
  == != & left-to-right \\
  \&\& & left-to-right \\
  || & left-to-right \\
\end{tabular}
\end{center}
Another problem is the dangling-else problem, which is characterized by which else should bind to which if:
\begin{verbatim}
 if exp then
    if exp then
   
    else
\end{verbatim} 
Which if does this else belong to. In general, one would always assume that it belongs to the nearest if, which is why unless otherwise specified this conflict is solved with this policy. 
\subsection{Implementation - Bison}
A bison file is divided into two parts. The first, which handles all parser declarations and the second part which contains the grammar rules. In the parser declaration tokens which are terminals and types which are non-terminals are declared.
For each type, a data type has to be indicated, those data types are binded with a structure in a union: 
\begin{lstlisting}
 %union {
	int intconst;
	char *stringconst; 
	struct FUNCTION *function;
	struct HEAD *head;
.
.
}

%token <intconst> tNUM
%token <stringconst> tID
%token tFUNC tEND tINT tBOOL tARRAY tRECORD tTYPE tVAR tRETURN 
%token tWRITE tALLOCATE tIF tTHEN tWHILE tDO tOFLENGTH tELSE tTRUE 
%token tFALSE tNULL tEQ tNEQ tGEQ tLEQ tAND tOR

%type <function> function
%type <head> head
.
.
\end{lstlisting}
The structures indicated are declared in the Abstract Syntax Tree.\\ The grammar is written context-free grammer, where each rule is associated with an action: 
\begin{lstlisting}
function: head body tail	

{if(strcmp($1->id, $3->id)!=0)
{printf("***SYNTAX ERROR***\nFUNCTION %s at line %d\n and END %s 
 at line %d\n does not share the same id, but is expected to share 
 same id\n",$1->id,$1->lineno,$3->id,$3->lineno);
 YYABORT;}$$ = makeFUNC($1,$2,$3);};
\end{lstlisting}
Every time function is called, it redirects to head, hereafter body and at last tail. The left part is the action that is executed, in general this is used to build the AST and in this case make sure that the function starts and ends with
the same name. The dollar sign makes the arguments available and the double dollar sign represents the stack. Everytime an AST action is executed it will be pushed on the stack. 
\section{Abstract Syntax tree}
An Abstract Syntax Tree is a tree representation of the syntactic structure of a program. AST is useful since it can build up a tree structure based on the grammar, every node represents a type whereas every leaf represents either an integer 
or an identifier. The root of the AST will be the structure of a body, since a body is defined to be able to contain everything.  
\subsection{Implementation}
For every type defined in the grammar a structure is created, since every type has specific purposes. The structures are specified based on the grammar, for instance: 
\begin{lstlisting}
type: tID										{$$ = makeTYPE_id($1);}
	| tINT										{$$ = makeTYPE_intconst();}
	| tBOOL										{$$ = makeTYPE_bool();}
	| tARRAY type								{$$= makeTYPE_array($2);}
	| tRECORD '{' var_decl_list'}'		{$$ = makeTYPE_record($3);};

typedef struct TYPE {
	int lineno;
	enum{type_idK,intK,boolK,arrayK,recordK} kind;
	union{
		char *id;
		struct TYPE *type;
		struct VAR_DECL_LIST *var_decl_list;
	}val;
}TYPE;
\end{lstlisting}
Type is defined to be five different kinds in the grammar. The definition of the structure type has 3 elements. A lineno, an enumerator telling which kind of type it is and a union which has all the possible datastructures the different kinds
can assume. Obviously, every type except array and record is named with an identifier. Array and Record is defined recursively, which is why they need another datastructure. Every type is defined corresponding to their grammar using this approach.\\
The next part of the AST is to create and assign the defined structures values. In the example of type is was obvious that every kind has a unique id and a data structure, since every type has its own branch in the grammar each type needs its own
method: 
\begin{lstlisting}
 TYPE *makeTYPE_bool(){
	TYPE *t;
	t = NEW(TYPE);
	t->lineno = lineno;
	t->kind = boolK;
	return t;
}
TYPE *makeTYPE_array(TYPE *type){
	TYPE *t;
	t = NEW(TYPE);
	t->lineno = lineno;
	t->kind = arrayK;
	t->val.type = type;
	return t;
}
\end{lstlisting}
The type bool doesn't take an argument, it only defines that a boolean not the specific value. The way to create this node is straight forward, a pointer is declared, memory is allocated and the kind is assigned. Looking at array, shows 
that the value also has to be assigned. This approach is used for the every creation of a node.
\section{Pretty printer - Implementation }
The pretty printer prints an AST, meaning all it has to do is to print the content of the nodes, parentheses and indentation. It recurses through the tree given a pointer to the root, every structure has a method for printing the structure:
\begin{lstlisting}
 void prettyTYPE(TYPE *type){
	switch(type->kind){
		case type_idK:
			printf("%s",type->val.id);
			break;
		case intK:
			printf("int");
			break;
		case boolK:
			printf("bool");
			break;
		case arrayK:
			printf("array of ");
			prettyTYPE(type->val.type);
			break;
		case recordK:
			printf("record of {");
			prettyVAR_DECL_LIST(type->val.var_decl_list);
			printf("}");
			break;
	}
}
\end{lstlisting}
 When printing TYPE, it takes a pointer to a its structure, depeding on which kind an action is taken. A simple type is handled with a print statement whereas a complex type, array and record, is handled with a recursive call. \\ Inorder
to create tabs based nested statements a help method is used called prettyTAB:
\begin{lstlisting}
 void prettyTAB(){
	int i;
	for(i=0;i<tabno;i++){
		printf("   ");
	}
}

void prettyFUNCTION(FUNCTION *func){
	prettyHEAD(func->head);
	tabno++;
	prettyBODY(func->body);
	tabno--;
	prettyTAIL(func->tail);
 }
\end{lstlisting}
All this method does is printing tabs, however it's keeping track on how deep the indentation is. PrettyTAB is called at the beginning of each pretty printer to give the right indentation. The variable tabno is increased or decreased 
everytime a while, if, else and function is called. 
\section{Test}
We have successfully tested this project-part with some of the provided tests on the course homepage:\\
\verb!AbsTest.raj!, \verb!ArrayIndex.raj!, \verb!Assoc.raj!, \verb!ErrOutOfBounds1.raj!, \verb!ErrOutOfBounds2.raj!, \verb!Factorial.raj!, \verb!Function.raj!, \verb!IfThen.raj!, \verb!KnapsackNoComments.raj!, \verb!Knapsack.raj!, \verb!SimpleRecord.raj!, \verb!StaticLink.raj!, \verb!WhileDo.raj!
\subsection{Dangeling else}
The input for this test is given in the appendix and is the file called \verb!dangeling_else_test.raj!.\\
In this test we have four \textbf{if} statements but only three \textbf{else} statements and we check the three innermost \textbf{if} statements is associated with the three \textbf{else} statements. Which means our expected 
output is where the three \textbf{else} has the same insertions as the three innermost \textbf{if} statements.
\subsubsection*{Output}
\begin{verbatim}
counter = 0;
n = 5;
b = null;
while(counter<n) do
   {
      if(counter<n) then
         if(counter<n) then
            if(counter>n) then
               return 32;
            else
               return 32;
         else
            if(counter>n) then
               write(90);
            else
               write(42);
      return 1337;
   }
\end{verbatim}
As expected the three \textit{else} statements is associated with the closest \textit{if} statements shown by the insertions.
\subsection{Comments}
The input for this test is given in the appendix and is the file called \verb!comments_test.raj!.\\
This test shows how we handle comments in the input file. As mentioned before we handle this in out flex file. Which means they shouldn't even get parsed, therefore the expected output is the same as the input but with no blank lines
and no comments(multiline-, nested- and singleline-comments).
\subsubsection*{Output}
\begin{verbatim}
var array:array of int;
var record:record of {a:int, b:bool};
counter = 0;
while(counter<10) do
   {
      write(42);
      counter = (counter+1);
      allocate blah of length 3;
   }
return null;
\end{verbatim}
As expected all comments is removed as they get eat'en up in our flex file.
\subsection{Indentation}
The input for this test is given in the appendix and is the file called \verb!indentation_test.raj!.\\
The purpose of this test is to show that out pretty-printer prints the output with indentation regardless of the indentation in the input. The input file contains statements with no newline which should be made in the output.
\subsubsection*{Output}
\begin{verbatim}
type lolz0r = bool;
func indentation(): int
   write(42);
   return 37;
end indentation 
write(1337);
while(42<1337) do
   {
      write(42);
   }
franz = lolz0r;
if(lolz0r == true) then
   {
      lolz0r = false;
      return 1337;
   }
else
   {
      return 42;
   }
\end{verbatim}
Above we see that the insertions is set correctly. When we enter a function the insertion of the \textit{<body>} is inceased and likewise for while statements, statement\_lists and the if and else statements.
\subsection{Precedence}
The input for this test is given in the appendix and is the file called \verb!precedence_test.raj!.\\
Here we check that our precedence hold according to the precedence table mentioned erlier in the report.
\subsubsection*{Output}
\begin{verbatim}
counter = 0;
n = 42;
write((42+1337));
write(((1337*42)+270289));
return ((((42/1337)*42)+((13*45)/32))+45);
if(n == counter) then
   return true;
else
   return false;
while((!counter) == 0) do
   return |(((((1337+(42*17))+(52/85))-(8965*85))+(556*5))+55)|;
if((4 || (0 && 4)) || 0) then
   return 42;
if((4 && 16) || (17 && 42)) then
   return 1337;
if((((!4) != ((5*4)+(14/45))) && 54) || (56 <= 45)) then
   return 270289;
if(!(counter>0)) then
   return true;
if((2 == 4) && (3 != 3)) then
   return false;
if((2 == 4) || (3 != 3)) then
   return false;
if(2 || ((4 != 3) && 3)) then
   return false;
if((counter >= 0) && (counter == 0)) then
   return true;
\end{verbatim}
As expected all the expressions above is correct according to our precedence table.
\subsection{Nested functions}
The input for this test is given in the appendix and is the file called \verb!nested_functions_test.raj!.\\
In this test we ensure that we can have nested functions. This is done by checking the indentation for the functions \textit{<head>} and \textit{<tail>}.
\subsubsection*{Output}
\begin{verbatim}
func a(): bool
   func b(): bool
      func c(): int
         return 42;
      end c 
      return false;
   end b 
   return true;
end a 
write(42);
\end{verbatim}
The indentation is corretly set, even when we have nested functions.
\subsection{Function id}
The input for this test is given in the appendix and is the file called \verb!function_id_test.raj!.\\
This test shows how we handle when a functions head and tail dosn't share the same \textbf{id}. It should give a syntax error, printing the \textbf{id} and line number of the \textit{<head>} and \textit{<tail>} showing that they are 
not equal.
\subsubsection*{Output}
\begin{verbatim}
***SYNTAX ERROR***
FUNCTION BKnap2 at line 9
 and END BKnap at line 46
 does not share the same id, but is expected to share same id
An error occurred in parsing
\end{verbatim}
As expected we dont even enter the pretty-printer as there is a syntax error.
\subsection{Nested statements}
The input for this test is given in the appendix and is the file called \verb!nested_statements_test.raj!.\\
The purpose of this test is the see how we can have a \textit{<statement\_list>} inside another \textit{<statement\_list>} and that the indentation is handled correctly.
\subsubsection*{Output}
\begin{verbatim}
counter = 0;
if(counter == 0) then
   {
      write(45);
      {
         {
            write(1337);
         }
         return true;
      }
   }
\end{verbatim}
The indentation is correct therefore nested statement\_lists is handled correct.
\newpage
\section{Appendix}
\subsection{rajahscanner.l}
\lstinputlisting{../rajahscanner.l}
\subsection{rajahparser.y}
\lstinputlisting{../rajahparser.y}
\subsection{memory.h}
\lstinputlisting{../memory.h}
\subsection{memory.c}
\lstinputlisting{../memory.c}
\subsection{tree.h}
\lstinputlisting{../tree.h}
\subsection{tree.c}
\lstinputlisting{../tree.c}
\subsection{pretty.h}
\lstinputlisting{../pretty.h}
\subsection{pretty.c}
\lstinputlisting{../pretty.c}
\subsection{main.c}
\lstinputlisting{../main.c}
\subsection{Makefile}
\lstinputlisting{../Makefile}
\subsection{dangeling\_else\_test.raj}
\lstinputlisting{../test/dangeling_else_test.raj}
\subsection{dangeling\_else\_test.raj}
\lstinputlisting{../test/dangeling_else_test.raj}
\subsection{comments\_test.raj}
\lstinputlisting{../test/comments_test.raj}
\subsection{indentation\_test.raj}
\lstinputlisting{../test/indentation_test.raj}
\subsection{precedence\_test.raj}
\lstinputlisting{../test/precedence_test.raj}
\subsection{nested\_functions\_test.raj}
\lstinputlisting{../test/nested_functions_test.raj}
\subsection{function\_id\_test.raj}
\lstinputlisting{../test/function_id_test.raj}
\subsection{nested\_statements\_test.raj}
\lstinputlisting{../test/nested_statements_test.raj}
\end {document}	